package com.zejian.structures.jichu;

/**
 * * @author  李某
 * * @date  2021/12/18 14:13
 * * 物有本末，事有终始。知其先后者，则近道亦。
 * * 荷花开满池塘的前一天，还是半塘荷花，半塘云！
 */

// 插入排序

public class InsertSort {

    public static void insertSort(int[] arr) {
        if (arr == null || arr.length == 0)
            return;

        for (int i = 1; i < arr.length; i++) { //假设第一个数位置时正确的；要往后移，必须要假设第一个。

            int j = i;
            int target = arr[i]; //待插入的

            //后移
            while (j > 0 && target < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }

            //插入
            arr[j] = target;
        }
    }
}

